#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MaxVex 200
#define INF 0x3f3f3f3f
//int G[MaxVex][MaxVex];
int visit[MaxVex] = { 0 };
int path[MaxVex];//记录节点
//int cnt[MaxVex];
int num[MaxVex] = { 0 };//统计节点
int sum[MaxVex] = { 0 };//临时储存城市中敌人驻军数量
//int tmp[MaxVex] = { 0 };
//char s[MaxVex][4];
//int Nv, Ne;
//int start, destination;
typedef struct Graph* PtrToGraph;
struct Graph {
int Nv;//顶点数
int Ne;//边数；
char S[MaxVex][4] ;//城市的名字
int Tmp[MaxVex] = { 0 };//驻扎敌人数
int G[MaxVex][MaxVex];//邻接矩阵
int Start, Destination;//起点、终点
int Cnt[MaxVex];//是否存在边
};
int getNum(char* c,Graph* graph) {
int i;//找到对应名称城市的序号
for (i = 0; i < graph->Nv; i++) {
    if (!strcmp(graph->S[i], c))
        return i;
}
}

PtrToGraph Init() {
char c1[4];
char c2[4];
PtrToGraph Mg;
Mg = (PtrToGraph)malloc(sizeof(struct Graph));
scanf("%d %d %s %s", &Mg->Nv, &Mg->Ne, c1, c2);
int i;
for (i = 0; i < Mg->Nv - 1; i++) {
    scanf("%s%d", Mg->S[i], &sum[i]);
    Mg->Tmp[i] = sum[i];
}
strcpy(Mg->S[Mg->Nv - 1], c1);
Mg->Start = getNum(c1,Mg);
Mg->Destination = getNum(c2,Mg);
memset(Mg->G, INF, sizeof(Mg->G));
int v1, v2, x;
for (i = 0; i < Mg->Ne; i++) {
    scanf("%s %s %d", c1, c2, &x);
    v1 = getNum(c1,Mg);
    v2 = getNum(c2,Mg);
    Mg->G[v1][v2] = x;//输入路径
    Mg->G[v2][v1] = Mg->G[v1][v2];//无向图
}
for (i = 0; i < Mg->Nv; i++) {
    if (Mg->G[Mg->Start][i] != INF)
        Mg->Cnt[i] = 1;//start->i存在边，则初始化路径数为1 
}
return Mg;
}
void Dijkstra(int start,Graph * Mg) {
visit[start] = 1;
num[start] = 1;
int i, j, w;
for (i = 0; i < Mg->Nv; i++) {
    int MIN = INF;
    for (j = 0; j < Mg->Nv; j++) {
        if (!visit[j] && Mg->G[start][j] < MIN) {
            MIN = Mg->G[start][j];
            w = j;
        }
    }
    visit[w] = 1;
    for (j = 0; j < Mg->Nv; j++) {
        if (!visit[j] && MIN + Mg->G[w][j] < Mg->G[start][j]) { //路径较短
            Mg->G[start][j] = MIN + Mg->G[w][j];//更新路径长度 
            Mg->Cnt[j] = Mg->Cnt[w];//统计路径数 
            path[j] = w;//记录上一个节点编号 
            sum[j] = sum[w] + Mg->Tmp[j];//更新杀敌数
            num[j] = num[w] + 1;//统计节点数 
        }
        else if (!visit[j] && MIN + Mg->G[w][j] == Mg->G[start][j]) { //路径长度一致
            Mg->Cnt[j] = Mg->Cnt[w] + Mg->Cnt[j];//统计路径数 
            if (num[w] + 1 > num[j]) { //经过节点较多
                num[j] = num[w] + 1;//统计节点数 
                path[j] = w;//记录上一个节点编号
                sum[j] = sum[w] + Mg->Tmp[j];//更新杀敌数 
            }
            else if (num[w] + 1 == num[j]) { //节点一样
                if (sum[w] > sum[path[j]]) { //杀敌人数较多
                    path[j] = w;//记录上一个节点编号
                    sum[j] = sum[w] + Mg->Tmp[j];//更新杀敌数
                }
            }
        }
    }
}
}
int main() {
Graph* Mg;
Mg=Init();//输入相关信息
int i;
for (i = 0; i < Mg->Nv; i++) {
    path[i] = Mg->Start;//
}
Dijkstra(Mg->Start,Mg);//寻找最短路径
int road[MaxVex] = { 0 };
int t = 0, r = Mg->Destination;
while (r != Mg->Start) {
    road[t++] = r;
    r = path[r];
}//储存最短路径中依次经过的城市名称
road[t] = Mg->Start;
for (i = t; i >= 0; i--) {
    printf("%s", Mg->S[road[i]]);
    if (i != 0)
        printf("->");
}
printf("\n");
printf("%d %d %d", Mg->Cnt[Mg->Destination], Mg->G[Mg->Start][Mg->Destination], sum[Mg->Destination]);
return 0;
}